0992. K 个不同整数的子数组【困难】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 滑动窗口

1. 📝 题目描述

• leetcode

给定一个正整数数组 nums 和一个整数 k，返回 nums 中「好子数组」的数目。

如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为「好子数组」。

• 例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。

子数组是数组的连续部分。

---

示例 1：

输入：nums = [1,2,1,2,3], k = 2
输出：7

解释：
恰好由 2 个不同整数组成的子数组：
[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

---

示例 2：

输入：nums = [1,2,1,3,4], k = 3
输出：3

解释：
恰好由 3 个不同整数组成的子数组：
[1,2,1,3], [2,1,3], [1,3,4]

---

提示：

• 1 <= nums.length <= 2 * 10^4
• 1 <= nums[i], k <= nums.length

2. 🎯 s.1 - 滑动窗口

js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraysWithKDistinct = function (nums, k) {
  // 恰好 k 个 = 最多 k 个 - 最多 k-1 个
  return atMostK(nums, k) - atMostK(nums, k - 1)
}

// 计算最多包含 k 个不同整数的子数组数量
function atMostK(nums, k) {
  const n = nums.length
  const map = new Map() // 记录窗口内每个数字的出现次数
  let left = 0
  let count = 0

  for (let right = 0; right < n; right++) {
    // 扩展右边界
    map.set(nums[right], (map.get(nums[right]) || 0) + 1)

    // 收缩左边界，保证窗口内不同数字不超过 k 个
    while (map.size > k) {
      map.set(nums[left], map.get(nums[left]) - 1)
      if (map.get(nums[left]) === 0) {
        map.delete(nums[left])
      }
      left++
    }

    // 以 right 为右端点，有 right - left + 1 个子数组
    count += right - left + 1
  }

  return count
}

• 时间复杂度：$O(n)$，其中 n 是数组长度，每个元素最多被访问两次
• 空间复杂度：$O(k)$，哈希表中最多存储 k 个不同的数字

算法思路：

• 核心公式：恰好 k 个不同整数 = 最多 k 个 - 最多 k-1 个
• 辅助函数：实现 atMostK(nums, k) 计算最多包含 k 个不同整数的子数组数量
• 滑动窗口：用 left 和 right 维护窗口，用哈希表记录窗口内每个数字的出现次数
• 窗口扩展：当不同数字超过 k 个时，收缩左边界直到满足条件
• 计数逻辑：以 right 为右端点的子数组有 right - left + 1 个，累加到结果中